package top.houry.linklist;

public class SingleLinkList<E> {

    private Node<E> data;

    static class Node<E> {
        private E data;
        private Node<E> next;

        public void setData(E data) {
            this.data = data;
        }

    }


    /**
     * 头结点插入
     *
     * @param e 插入数值
     */
    public void addFirst(E e) {
        Node<E> node = new Node<>();
        node.setData(e);
        node.next = data;
        data = node;
    }


    /**
     * 尾结点插入
     *
     * @param e 插入数值
     */
    public void addLast(E e) {
        Node<E> node = new Node<>();
        node.setData(e);
        if (null == data) {
            data = node;
        } else {
            // 这里必须声名一个临时的变量用来循环，否则（使用data）会影响运算结果
            Node<E> currentNode = data;
            while (true) {
                if (null == currentNode.next) {
                    currentNode.next = node;
                    break;
                }
                currentNode = currentNode.next;
            }
        }
    }


    public Node<E> get() {
        return data;
    }

    public void print(Node<E> e) {
        if (null == e) {
            throw new RuntimeException("数据为空");
        }
        while (true) {
            if (null != e.next) {
                System.out.print(e.data + "->");
                e = e.next;
            } else {
                System.out.print(e.data);
                break;
            }
        }

        System.out.println();
    }


    public Node<E> flip(Node<E> e) {
        if (null == e) {
            return e;
        }
        Node<E> prev = null;
        Node<E> cur = e;
        while (null != cur) {
            Node<E> temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }


    public Node<E> flip(Node<E> head, int m, int n) {
        if (null == head || m >= n) {
            return head;
        }
        Node<E> dummy = new Node<>();
        dummy.next = head;
        head = dummy;

        for (int i = 1; i < m; i++) {
            head = head.next;
        }

        Node<E> prev = null;
        Node<E> curr = head.next;
        Node<E> last = curr;
        for (int i = m; i <= n; i++) {
            Node<E> temp = curr.next;
            curr.next = prev;
            prev = curr;

            curr = temp;
        }

        head.next = prev;
        last.next = curr;
        return dummy.next;


    }

    public static void main(String[] args) {
        SingleLinkList<Integer> list = new SingleLinkList<>();
//        list.addFirst(1);
//        list.addFirst(2);
//        list.addFirst(3);
//        list.addFirst(4);
//        list.addFirst(5);

        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(5);
        list.addLast(6);
        list.addLast(7);
        list.addLast(8);
//
//        list.print(list.get());
//
//        System.out.println();
//
        list.print(list.get());
        list.print(list.flip(list.get(), 4, 7));

    }


}


